﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace AZProjekt
{
    public class MinEdgeCutAlgorithm
    {
        private int[][] _edges; //połączenia wierzchołków
        private int _source; //indeks ujścia
        private int _sink; // indeks ujścia
        private int _length; //liczba wierzchołków
        private int _minEdgeCut; //spojnosc krawedziowa


        /// <summary>
        /// Metoda, wykonująca algorytm, bazujący na algorytmie Forda-Fulkersona. Znajduje spójność krawędziową grafu przez przepływ.
        /// </summary>
        /// <param name="edges">Tablica, określająca krawędzie między wierzchołkami.</param>
        /// <param name="length">Liczba wierzchołków w grafie.</param>
        /// <returns>-1: gdy graf jest niespójny; liczba nieujemna: określa znalezioną spójność krawędziową</returns>
        public int DoAlgorithm(int[][] edges)
        {
            _length = edges[0].Length;
            if (_length < 2)
                return 0;

            _minEdgeCut = int.MaxValue; //spójność krawędziowa
            int[][] originalEdges = edges.Select(a => a.ToArray()).ToArray();
            _source = 0;

            for (_sink = _length - 1; _sink > 0; _sink--)
            {
                _edges = originalEdges.Select(a => a.ToArray()).ToArray(); //kopia originalEdges
                if ((_minEdgeCut = findMinEdgeCut()) == -1)
                    break;
            }
            return _minEdgeCut;
        }

        private int findMinEdgeCut()
        {
            int tempMinEdgeCut = 0;

            while (findPath() == 1)
                tempMinEdgeCut++;

            if (tempMinEdgeCut == 0)
                return -1;

            return _minEdgeCut > tempMinEdgeCut ? tempMinEdgeCut : _minEdgeCut;
        }

        private void initializeVertices(List<Vertex> vertices)
        {
            for (int i = 0; i < _length; i++)
            {
                vertices.Add(new Vertex
                {
                    Distance = int.MaxValue,
                    Predecessor = -1,
                    Index = i,
                });
            }
            vertices.First(n => n.Index == _source).Distance = 0;
        }

        /// <summary>
        /// Wyszukuje najkrótszą ścieżkę między wierzchołkami o indeksach source i sink (algorytm Dijkstry).
        /// </summary>
        /// <returns>0: jeśli nie ma ścieżki między current i sąsiadem; 1: w przeciwnym wypadku</returns>
        private int findPath() //argumenty podane dla lepszego zrozumienia
        {
            var vertices = new List<Vertex>();
            var examinedVertices = new List<Vertex>();
            initializeVertices(vertices);

            while (vertices.Any())
            {
                vertices.Sort();
                var first = vertices[0];
                if (first.Distance == int.MaxValue)
                    break;

                examinedVertices.Add(first);
                var neighbors = getNeighbors(first, vertices);
                foreach (var neighbor in neighbors)
                {
                    var distance = first.Distance + 1;
                    if (distance < neighbor.Distance)
                    {
                        neighbor.Distance = distance;
                        neighbor.Predecessor = first.Index;
                    }
                }
                vertices.RemoveAt(0);
            }

            var vertex = examinedVertices.FirstOrDefault(n => n.Index == _sink);
            if (vertex == null)
                return 0;
            while (vertex.Predecessor != -1)
            {
                _edges[vertex.Index][vertex.Predecessor] = _edges[vertex.Predecessor][vertex.Index] = 0;
                vertex = examinedVertices.First(m => m.Index == vertex.Predecessor);
            }

            return 1;
        }

        /// <summary>
        /// Wyszukuje sąsiadów wierzchołka vertex.
        /// </summary>
        /// <param name="vertex">Wierzchołek</param>
        /// <param name="vertices">Lista wierzchołków</param>
        /// <returns>Lista sąsiadów wierzchołka vertex.</returns>
        private List<Vertex> getNeighbors(Vertex vertex, List<Vertex> vertices)
        {
            return vertices.Where(node => !node.Equals(vertex) && _edges[vertex.Index][node.Index] == 1).ToList();
        }
    }
}
